We present a fast general-purpose algorithm for high-throughput clustering ofdata "with a two dimensional organization". The algorithm is designed to beimplemented with FPGAs or custom electronics. The key feature is a processingtime that scales linearly with the amount of data to be processed. This meansthat clustering can be performed in pipeline with the readout, withoutsuffering from combinatorial delays due to looping multiple times through allthe data. This feature makes this algorithm especially well suited for problemswhere the data has high density, e.g. in the case of tracking devices workingunder high-luminosity condition such as those of LHC or Super-LHC. Thealgorithm is organized in two steps: the first step (core) clusters the data;the second step analyzes each cluster of data to extract the desiredinformation. The current algorithm is developed as a clustering device formodern high-energy physics pixel detectors. However, the algorithm has muchbroader field of applications. In fact, its core does not specifically rely onthe kind of data or detector it is working for, while the second step can andshould be tailored for a given application. Applications can thus be foreseento other detectors and other scientific fields ranging from HEP calorimeters tomedical imaging. An additional advantage of this two steps approach is that thetypical clustering related calculations (second step) are separated from thecombinatorial complications of clustering. This separation simplifies thedesign of the second step and it enables it to perform sophisticatedcalculations achieving online-quality in online applications. The algorithm isgeneral purpose in the sense that only minimal assumptions on the kind ofclustering to be performed are made.
展开▼
